A forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures. Families vary in the nature of what is forbidden. In general, a structure G is a member of a family if and only if a forbidden substructure is not contained in G. The forbidden substructure might simply be a subgraph, or a substructure from which one might derive (via, e.g., edge contraction or subdivision) that which is forbidden. Thus, the forbidden structure might be one of:
(Such forbidden structures can also be called obstruction sets.)
Forbidden graph characterizations are utilized in combinatorial algorithms, often for identifying a structure. Such methods can provide a polynomial-time algorithm for determining a graph's membership in a specific family (i.e., a polynomial-time implementation of an indicator function).
A well-known characterization of this kind is the Kuratowski theorem that provides two forbidden homeomorphic subgraphs, using which, one may determine a graph's planarity. Another is the Robertson–Seymour theorem that proves the existence of a forbidden minor characterization for several graph families.
Family | Forbidden graphs | Relation | Reference | |
---|---|---|---|---|
Forests | loops, pairs of parallel edges, and cycles of all lengths | subgraph | Definition | |
a loop (for multigraphs) or a triangle K3 (for simple graphs) | graph minor | Definition | ||
Claw-free graphs | star K1,3 | induced subgraph | Definition | |
Comparability graphs | induced subgraph | |||
Triangle-free graphs | triangle K3 | induced subgraph | Definition | |
Planar graphs | K5 and K3,3 | homeomorphic subgraph | Kuratowski theorem | |
K5 and K3,3 | graph minor | Wagner's theorem | ||
Outerplanar graphs | K4 and K2,3 | graph minor | Diestel (2000),[1] p. 107 | |
Graphs of fixed genus | a finite obstruction set | graph minor | Diestel (2000),[1] p. 275 | |
Apex graphs | a finite obstruction set | graph minor | [2] | |
Linklessly embeddable graphs | The Petersen family | graph minor | [3] | |
Bipartite graphs | odd cycles | subgraph | [4] | |
Chordal graphs | cycles of length 4 or more | induced subgraph | [5] | |
Perfect graphs | cycles of odd length 5 or more or their complements | induced subgraph | [6] | |
Line graph of graphs | nine forbidden subgraphs (listed here) | induced subgraph | [7] | |
Graph unions of cactus graphs | the four-vertex diamond graph formed by removing an edge from the complete graph K4 | graph minor | [8] | |
Ladder graphs | K2,3 and its dual graph | homeomorphic subgraph | [9] | |
Helly circular-arc graphs | induced subgraph | [10] | ||
split graphs | induced subgraph | [11] | ||
treewidth ≤ 2 (branchwidth ≤ 2) | K4 | graph minor | Diestel (2000),[1] p. 327 | |
treewidth ≤ 3 | K5, octahedron, pentagonal prism, Wagner graph | graph minor | [12] | |
branchwidth ≤ 3 | K5, octahedron, cube, Wagner graph | graph minor | [13] | |
Complement-reducible graphs (cographs) | 4-vertex path P4 | induced subgraph | [14] | |
Trivially perfect graphs | 4-vertex path P4 and 4-vertex cycle C4 | induced subgraph | [15] | |
Threshold graphs | 4-vertex path P4, 4-vertex cycle C4, and complement of C4 | induced subgraph | [15] | |
Line graph of 3-uniform linear hypergraphs | a finite list of forbidden induced subgraphs with minimum degree at least 19 | induced subgraph | [16] | |
Line graph of k-uniform linear hypergraphs, k > 3 | a finite list of forbidden induced subgraphs with minimum edge degree at least 2k2 − 3k + 1 | induced subgraph | [17] [18] | |
General theorems | ||||
a family defined by an induced-hereditary property | a (not necessarily finite) obstruction set | induced subgraph | ||
a family defined by an minor-hereditary property | a finite obstruction set | graph minor | Robertson–Seymour theorem |